package dynamic;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.Test;

import utils.ArrayGenerator;
public class Ex312 {
    class Solution1 {
        //超时，没有想到时间优化方案
        public int maxCoins_1(int[] nums) {
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            map = new HashMap<>();
            return dfs(list, 0);
        }

        Map<List<Integer>, Integer> map;
        public int dfs(List<Integer> list, int cur) {
            if (list.size() == 0) {
                return cur;
            }
            loop: for(List<Integer> l: map.keySet()) {
                boolean equals = true;
                if (l.size() != list.size()) continue;
                else {
                    for (int i = 0; i < l.size(); i++) {
                        if (list.get(i) != l.get(i)) {
                            equals = false;
                            continue loop;
                        }
                    }
                }
                if (equals) {
                    return map.get(l);
                }
            }
            int left, right, n, sum, max = 0, res, temp;
            for (int i = 0; i < (n = list.size()); i++) {               
                left = i > 0 ? list.get(i - 1) : 1;
                right = i < n - 1 ? list.get(i + 1) : 1;
                sum = left * right * list.get(i);
                temp = list.remove(i);
                res = dfs(list, cur + sum);
                max = Math.max(max, res);
                list.add(i, temp);
            }
            map.put(new ArrayList<>(list), max);
            return max;
        }

        public int maxCoins(int[] nums) {
            return 0;
        }
    }

    class Solution {

        public int maxCoins(int[] nums) {
            int len = nums.length;
            //复制一个新的数组，不用考虑边界【如代码逻辑中，指针指向nums最后一个元素，此时需要考虑右界元素为1，而在右边添加上1，就可以在nums范围内遍历时，使用newNum来进行元素查找，无需思考边界】
            int newNum[] = new int[len + 2];
            System.arraycopy(nums, 0, newNum, 1, len);
            newNum[0] = 1;
            newNum[len + 1] = 1;
            nums = newNum;
            int[][] f = new int[len + 2][len + 2];
            for (int n = 3; n <= len + 2; n++) { //区间的大小
                for (int i = 0; i <= len + 2 - n; i++) { //区间左端点，不能超出区间,且至少右边有2个点
                    //由区间左端点和右端点可得区间的右端点为 i + n - 1
                        int res = 0;
                        for (int k = i + 1; k < i + n - 1; k++) {
                            //状态转移方程解释：
                            /* 
                                区间内只考虑最后一个删除的元素k，此时，无论k左右两边怎样的删除顺序都不会影响另一边
                                f[i][j] 是指在 (i, j) ***开区间***内得到的最优答案【之所以开，是因为不必考虑i, j参与进来求最优，i，j本身的作用就是单纯计算删除k能得到的奖励】
                                即将问题通过k分治为左右两个部分
                                而i, k, j的大问题变成了(i, k) (k, j) 两个子问题                               
                            */
                            res = f[i][k] + nums[i] * nums[k] * nums[i + n - 1]+ f[k][i + n - 1];
                            f[i][i + n - 1] = Math.max(res, f[i][i + n - 1]);
                        }
                }
            }
            return f[0][len + 1]; //原数组作为区间的值
        }

        // Map<List<Integer>, Integer> map;
        // public int dfs(boolean[] flag, List<Integer> path, int sum, int count) {
           /*  上午写了一上午，只写出两个超时的题，心中的挫败感可想而知。
                本人脑子不是很聪明，动态规划题感觉总是想不到状态空间怎么表示，只有常见的类型如最长【尾元素最长】、共同【f[i][j]
                表示两条序列的第i个第j个】如此这种题，才能马上想到状态空间，否则根本想不到

                像这题，我只能选择dfs方法，然而到了15个左右就超时了。
                于是，我之后一直在想如何记忆化
            
                我定义的递归参数是：public int dfs(List<Integer> list, int cur) 
                list表示删除某个元素之后的数组，cur是当前的收益
                我一直在想的问题就是如何记录list和返回值之间的映射，在方法刚开始时就可以退出，减少时间消耗，
                就如同平时使用数组来记忆化，只不过我想记录的内容很长而已


                如果能想到的话，以后不必考虑动态规划这样的“随缘解法”，而是每题都有固定的解法

                我另一道超时的题是上一题股票冷冻期的问题，这题明显是动态规划，但是题目的条件太多，我实在想不出怎么用状态空间来表示出来
                于是又再次使用dfs，我列的式子是：

                    * @param h 持有股票吗
                    * @param hold <0，持有股票，未卖出； =0,不持有股票[有bug，若股票价格为0，检测不出来，需要另外的标志]
                    * @param profit 当前利润
                    * @param idx 遍历到的数组下标
                    * @param flag 是否在冷冻期

                    思路很简单，但是仍然是O(n!)级别的算法，毫不意外超时了
                    
                    说到这里，我想求助大家的是，如何用一种java的方法，能够存储一种映射关系，将这种多参数和其对应的dfs结果记忆化，
                    然后在dfs刚开始时返回呢？

                    我开始的想法是，建立Node类，利用HashMap来映射，但是HashMap存储的是引用，与值本身无关，因此新建Node永远都不会找到匹配的值；
                    于是我考虑比对每一个参数: 遍历map每个key，将key的每个属性与当前dfs方法每个参数比对，全部匹配再返回
                    但是这样至少是O(n^3)的复杂度，仍然很长
                    
                    我又想到了md5之类的摘要方法，但是摘要貌似只能摘要一个结果

                    请问各位大佬，有没有方法可以实现以上的功能呢？
           */
        // }
    }

@Test
public void test() {
    Solution s = new Solution();
    int[] nums = new int[]{3,1,5,8};
    // nums = new int[]{7, 8, 7, 2, 7, 2, 5, 9, 1, 3, 3, 4, 2, 3, 0, 6, 6, 9, 0, 2};
    // nums = new int[]{1,5};
    // nums = ArrayGenerator.getArray(10, 10);
    // System.out.println(Arrays.toString(nums));
    long start = System.currentTimeMillis();
    System.out.println(s.maxCoins(nums));
    System.out.println(System.currentTimeMillis() - start);
}

}
